package ACWing.TheNnderlyingAlgorithm.归并;
//787. 归并排序

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/11/17 12:51
 */
public class MergeSorting {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]arr=new int[n];

        for (int i = 0; i < n; i++) {
            arr[i]=sc.nextInt();
        }
        sort(arr,0,n-1);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    private static void sort(int[] arr, int l, int r) {
       if(l>=r){
           return;
       }
       int mid=l+r>>1;
       sort(arr,l,mid);sort(arr,mid+1,r);//先将左右俩段数组排序
       int i=l,j=mid+1,k=0;//数组合并开始（排序的核心作用处）
       int[]temp=new int[r-l+1];
       while (i<=mid&&j<=r){
           if(arr[i]>arr[j]){
               temp[k]=arr[j];
               k++;
               j++;
           }else {
               temp[k]=arr[i];
               k++;
               i++;
           }
       }
       while (i<=mid){
           temp[k]=arr[i];
           k++;i++;
       }while (j<=r){
           temp[k]=arr[j];
           k++;j++;
        }
        for (int m = l,p=0; m <= r;m++,p++) {
            arr[m]=temp[p];
        }
    }
}
